package array;

import java.net.Inet4Address;
import java.util.HashMap;

public class 打印出现次数超过一半的数 {
	public static void printAppearTimesMoreThanHalf (int[] arr){
		//求出中位数就可以了
		
		int times = 0; 
		int cand = 0;
		for(int i=0;i<arr.length;i++) {
			if(times ==0) {
				cand = arr[i];
				times =1;
			}else if(cand == arr[i]) {
				times++;
			}else {
				times--;
			}
		}
		times=0;
		for(int i=0;i<arr.length;i++) {
			if(arr[i] == cand) {
				times++;
			}
		}
		if(times>arr.length/2) {
			System.out.println(cand);
		}else{
			System.out.println("Not Found");
		}
	}
	
	
	public static void printKMajor(int[] arr, int k){
		if(k < 2) {
			System.out.println("The value of K is invalid");
		}
		
		HashMap<Integer, Integer> cands = new HashMap<>();
		
		for(int i=0;i!=arr.length;i++) {
			
		}
	}
	public static void main(String[] args) {
		int[] arr = { 1, 2, 3};
		printAppearTimesMoreThanHalf(arr);
	}
}
